class SpaceMap(object):
	''' Here we have:
	__bottom - minimum space address possible;
	__top - maximum space address possible;
	__pairs - internal list of ranges;
	__walk_list - internal list of keys.'''

	__slots__ = frozenset(('__bottom', '__pairs', '__top', '__walk_list'))

	def __init__(self, source = None, bottom = 0, top = None):
		''' This one can be bootstrapped by giving a dict in format {x:y, x:y}.'''
		self.__pairs = {}
		self.__walk_list = None
		self.__bottom = bottom
		self.__top = top
		if type(source) == dict:
			for key in source:
				self.__set(key, source[key])
			self.fold()

	def __getitem__(self, name):
		'''Returns last range address by first range address.'''
		if name in self.__pairs:
			return(self.__pairs[name])
		else:
			return(None)

	def __set(self, name, value):
		'''Internal function to add ranges without folding. Also checks for range correctness.'''
		if type(name) != int or type(value) != int or name >= value:
			return(False)
		if self.__bottom != None:
			if name < self.__bottom or value < self.__bottom:
				return(False)
		if self.__top != None:
			if name >= self.__top or value >= self.__top:
				return(False)
		self.__pairs[name] = value
		return True

	def __setitem__(self, name, value):
		'''Adds one more range and tries to fold a space map.'''
		self.__set(name, value)
		self.fold()

	def fold(self):
		'''Tries to normalize spacemap by joining coaligned or overlapping ranges.'''
		self.rewind()
		pairs = ()
		while True:
			pair = self.pop()
			if pair[0] == None:
				break
			pairs += pair,
		last_pair = self.__bottom
		for pair in pairs:
			if last_pair in self.__pairs and pair[0] <= self.__pairs[last_pair]:
				if pair[1] > self.__pairs[last_pair]:
					self.__pairs[last_pair] = pair[1]
					del(self.__pairs[pair[0]])
			else:
				last_pair = pair[0]
		self.clear()

	def rewind(self):
		'''Reinitialises internal ordered list of ranges.'''
		self.__walk_list = list(self.__pairs.keys())
		self.__walk_list.sort()

	def clear(self):
		'''Clears internal ordered list of ranges.'''
		self.__walk_list = None

	def pop(self):
		'''Returns next range from ordered list of ranges.'''
		if self.__walk_list != None:
			if len(self.__walk_list) > 0:
				next = self.__walk_list.pop(0)
				return([next, self.__pairs[next]])
		return([None, None])

	def __repr__(self):
		'''Returns the inner dict with ranges.'''
		return(repr(self.__pairs))

	def __and__(self, other):
		'''Returns new space map with ranges that appears both in A and B.'''
		if type(other) != SpaceMap:
			return(False)
		new = {}
		self.rewind()
		other.rewind()
		my_pair = self.pop()
		other_pair = other.pop()
		# if there are no pairs in B - we have nothing to do
		if other_pair[0] == None or my_pair[0] == None:
			all_parts_found = True
		else:
			all_parts_found = False
		while not all_parts_found:
			if my_pair[0] > other_pair[0]:
				# when my pair starts after other pair starts
				#  m---
				# o---
				if my_pair[0] > other_pair[1]:
					# when my pair starts after other pair ends
					#       m---
					# o---o
					other_pair = other.pop()
					# tossing out other pair
					if other_pair[0] == None:
						all_parts_found = True
				else:
					# when my pair starts before other pair ends
					#    m--- |     m---
					# o---o   | o---o
					if my_pair[1] > other_pair[1]:
						# when my pair ends after other pair ends
						#    m---m |     m---m
						# o---o    | o---o
						other_pair[0] = my_pair[0]
						# trimming other pair by my pair start
						#   m---m
						# o.o-o
					else:
						# when my pair ends before other pair ends
						#  m---m
						# o-----o
						new[my_pair[0]] = my_pair[1]
						# my pair is covered and should be added to result
						my_pair = self.pop()
						# tossing out my pair
						if my_pair[0] == None:
							all_parts_found = True
			elif my_pair[0] < other_pair[0]:
				# when my pair starts before other one
				# m---
				#  o---
				if my_pair[1] < other_pair[0]:
					# when my pair ends before other pair starts
					# m---m
					#       o---
					my_pair = self.pop()
					# tossing out my pair
					if my_pair[0] == None:
						all_parts_found = True
				else:
					# when my pair ends before other pair starts
					# m---m
					#   o---
					my_pair[0] = other_pair[0]
					# trimming my pair by other pair start
					# m.m-m
					#   o---
			else:
				# when both pairs starts simultaneously
				# m---
				# o---
				if my_pair[1] < other_pair[1]:
					# when my pair ends before other pair
					# m---m
					# o-----o
					new[my_pair[0]] = my_pair[1]
					# my pair is covered and should be added to result
					my_pair = self.pop()
					# tossing out my pair
					if my_pair[0] == None:
						all_parts_found = True
				else:
					# when my pair ends after other pair
					# m-----m
					# o---o
					new[my_pair[0]] = other_pair[1]
					# part of my pair is covered and should be added to result
					other_pair = other.pop()
					# tossing out other pair
					if other_pair[0] == None:
						all_parts_found = True
		self.clear()
		other.clear()
		return(SpaceMap(new, self.__bottom, self.__top))

	def __sub__(self, other):
		'''Returns new space map with ranges in A not covered by B.'''
		if type(other) != SpaceMap:
			return(False)
		new = {}
		self.rewind()
		other.rewind()
		my_pair = self.pop()
		other_pair = other.pop()
		# if there are no pairs in B - copy this one to new SpaceMap
		if other_pair[0] == None:
			new[my_pair[0]] = my_pair[1]
			all_parts_found = True
		elif my_pair[0] == None:
			all_parts_found = True
		else:
			all_parts_found = False
		while not all_parts_found:
			if my_pair[0] > other_pair[0]:
				# when my pair starts after other pair starts
				#  m---
				# o---
				if my_pair[0] > other_pair[1]:
					# when my pair starts after other pair ends
					#       m---
					# o---o
					other_pair = other.pop()
					# tossing out other pair
					if other_pair[0] == None:
						# this was last one - my pair goes to result
						new[my_pair[0]] = my_pair[1]
						all_parts_found = True
				else:
					# when my pair starts before other pair ends
					#    m--- |     m---
					# o---o   | o---o
					if my_pair[1] > other_pair[1]:
						# when my pair ends after other pair ends
						#    m---m |     m---m
						# o---o    | o---o
						my_pair[0] = other_pair[1]
						# trimming my pair by other pair end
						#   m.m-m
						# o---o
						other_pair = other.pop()
						# tossing out other pair
						if other_pair[0] == None:
						# this was last one - my pair goes to result
							new[my_pair[0]] = my_pair[1]
							all_parts_found = True
					else:
						# when my pair ends before other pair ends
						#  m---m
						# o-----o
						my_pair = self.pop()
						# tossing out my pair
						if my_pair[0] == None:
							all_parts_found = True
			elif my_pair[0] < other_pair[0]:
				# when my pair starts before other one
				# m---
				#  o---
				if my_pair[1] < other_pair[0]:
					# when my pair ends before other pair starts
					# m---m
					#       o---
					new[my_pair[0]] = my_pair[1]
					# my pair is not covered and should be added to result
					my_pair = self.pop()
					# tossing out my pair
					if my_pair[0] == None:
						all_parts_found = True
				else:
					# when my pair ends before other pair starts
					# m---m
					#   o---
					new[my_pair[0]] = other_pair[0]
					# start of my pair is not covered and should be added to result
					my_pair[0] = other_pair[0]
					# trimming my pair by other pair start
					# m.m-m
					#   o---
			else:
				# when both pairs starts simultaneously
				# m---
				# o---
				if my_pair[1] < other_pair[1]:
					# when my pair ends before other pair
					# m---m
					# o-----o
					my_pair = self.pop()
					# tossing out my pair
					if my_pair[0] == None:
						all_parts_found = True
				else:
					# when my pair ends after other pair
					# m-----m
					# o---o
					my_pair[0] = other_pair[1]
					# trimming my pair by other pair end
					# m...m-m
					# o---o
					other_pair = other.pop()
					# tossing out other pair
					if other_pair[0] == None:
						# this was last one - my pair goes to result
						new[my_pair[0]] = my_pair[1]
						all_parts_found = True
		while True:
			# copy any leftover in A to new SpaceMap
			my_pair = self.pop()
			if my_pair[0] == None:
				break
			else:
				new[my_pair[0]] = my_pair[1]
		self.clear()
		other.clear()
		return(SpaceMap(new, self.__bottom, self.__top))

	def __eq__(self, other):
		'''Compares two space maps.'''
		if type(other) != SpaceMap:
			return(False)
		self.rewind()
		other.rewind()
		result = None
		while True:
			this = self.pop()
			that = other.pop()
			if this != that:
				result = False
				break
			if this == [None, None] and that == [None, None]:
				result = True
				break
		self.clear()
		other.clear()
		return(result)

	def __ne__(self, other):
		return(not self == other)

	def end(self):
		'''Returns last known point.'''
		end = None
		self.rewind()
		while True:
			this = self.pop()
			if this == [None, None]:
				break
			elif end == None or this[1] > end:
				end = this[1]
		self.clear()
		return(end)

	def __len__(self):
		return(len(self.__pairs))

	def max(self):
		result = None
		for last in self.__pairs.itervalues():
			if result == None or result < last:
				result = last
		return(result)
